#include <stdio.h>
#include <stdlib.h>

typedef struct listNode{
	int* dataPtr;
	struct listNode* next;
}ListNode;

typedef struct list
{
	ListNode* head;
	ListNode* tail;
}List;

void makeEmptyList(List *lst)
{
	lst->head = lst->tail = NULL;
}

void insertDataToEndList(List *lst, int num)
{
	ListNode *new;
	new = malloc(sizeof(ListNode));
	new->dataPtr = malloc(sizeof(int));
	*(new->dataPtr) = num;
	new->next = NULL;
	if(lst->tail)
	{
		lst->tail->next = new;
		lst->tail = new;
	}
	else
		lst->head = lst->tail = new;
}

List getList()
{
    List res;
    int size, num, i;

    makeEmptyList(&res);

    printf("Please enter the number of items to be entered:\n");
    scanf("%d", &size);

    printf("Please enter the numbers:\n");
    for(i = 0; i < size; i++)
    {
	    scanf("%d", &num);
	    insertDataToEndList(&res, num);
    }
    return res;

}

List merge(List lst1, List lst2)
{
	List ret;
	makeEmptyList(&ret);
	if(lst1.head && !lst2.head)
	{
		ret.head = lst1.head;
		lst1.head = lst1.head->next;
		ret.head->next = merge(lst1, lst2).head;
	}
	else if(lst2.head)
	{
		ret.head = lst2.head;
		lst2.head = lst2.head->next;
		ret.head->next = merge(lst1, lst2).head;
	}
	else if(*(lst1.head->dataPtr) > *(lst2.head->dataPtr))
	{
		ret.head = lst1.head;
		lst1.head = lst1.head->next;
		ret.head->next = merge(lst1, lst2).head;
	}
	else if(*(lst1.head->dataPtr) < *(lst2.head->dataPtr))
	{
		ret.head = lst2.head;
		lst2.head = lst2.head->next;
		ret.head->next = merge(lst1, lst2).head;
	}

	return ret;
}

void printList(List *lst)
{
	ListNode *cur;
	cur = lst->head;
	while(cur)
	{
		printf("%d ", *(cur->dataPtr));
		cur = cur->next;
	}
	printf("\n");
}

void freeList(List *lst)
{
	ListNode *cur, *temp;
	cur = lst->head;
	while(cur)
	{
		temp = cur->next;
		free(cur->dataPtr);
		free(cur);
		cur = temp;
	}
}


int main()
{

    List lst1, lst2, mergedList;

    lst1 = getList();
    lst2 = getList();

    mergedList = merge(lst1,lst2);

    printf("Merged list:\n");
    printList(&mergedList);

    freeList(&lst1);
    freeList(&lst2);
    freeList(&mergedList);

	return 0;
}


